//所有排序重小到大
public class Sort {
    //选择排序
    public static void selectsort1(int[] array){
        int left = 0;
        for (int i = 0; i < array.length; i++) {
            int minindex = i;
            //遍历一趟找到相比下的最小值
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minindex]){
                    //换下标
                    minindex = j;
                }
            }
            //交换
            swap(array,minindex,i);
        }
    }
    //优化版选择排序
    public static void selectsort2(int[] array){
        int left = 0;
        int right = array.length-1;
        while (left < right){
            int minindex = left;
            int maxindex = left;
            int i = left;
            while (i <= right){
                //找最小下标
                if (array[i] < array[minindex]){
                    minindex = i;
                }
                //找最大下标
                if (array[i] > array[maxindex]){
                    maxindex = i;
                }
                i++;
            }
            //最小值更换
            swap(array,left,minindex);
            //可能在最小值更换的时候把接下来要更换的最大下标更换掉了
            if(maxindex == left){
                maxindex = minindex;
            }
            //最大值更换
            swap(array,right,maxindex);
            left++;
            right--;
        }
    }
    //直接插入排序
    public static void insertsort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                //如果后大于前要交换
                if(array[j] > tmp) {
                    array[j + 1] = array[j];
                }else{
                    //把被替换的这个值与前面已交换过的元素再比较，
                    array[j+1] = tmp;
                    break;
                }
            }
            /*
            * 1.无论循环是否结束都会执行该代码
            * 2.for循环结束说明这次被替换下来的值没有比前面的值大，即是最小的放在第一位
            * 3.当通过break结束时 只是重新赋值不影响
            * */
            //
            array[j + 1] = tmp;
        }
    }
    //希尔排序
    public static void shellSort(int[] array,int gap){
        //当趟数为1使排序结束
        while (gap > 1){
            gap = gap / 2;
            //i+1表示不是对一组值进行直接插入排序，而是交替对每一组进行
            for (int i = gap; i < array.length; i++) {
                int tmp = array[i];
                int j = i - gap;
                for (; j >= 0; j-=gap) {
                    //如果后大于前要交换
                    if(array[j] > tmp) {
                        array[j + gap] = array[j];
                    }else{
                        //把被替换的这个值与前面已交换过的元素再比较，
                        array[j + gap] = tmp;
                        break;
                    }
                }
                //此时把被换下来的值最小把它放在该组的第一位置
                array[j + gap] = tmp;
            }
        }
    }
    //堆排序(以键小根堆，排降序为例)
    public static void heapSort(int[] array){
        int len = array.length;
        creatHeap(array,len);
        while(len > 0){
            swap(array,0,len-1);
            shiftUp(array,0,len-1);
            len--;
        }
    }
    //通过向下调整建堆
    public static void creatHeap(int[] array,int len){
        int parent = (len - 1 - 1) / 2;
        for (int i = parent; i >= 0 ;i--) {
            shiftUp(array,i,len);
        }
    }
    //向下调整
    public static void shiftUp(int[] array,int parent,int len){
        int child = parent * 2 +1;
        while(child < len){
            //找左右最小孩子
            if(child+1 < len && array[child] > array[child+1]) {
                child++;
            }
            //如果父节点小于孩子结点则交换
            if (array[parent] > array[child]){
                swap(array,parent,child);
            }
            parent = child;
            child = parent * 2 +1;
        }
    }
    //冒泡排序
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j+1]){
                    swap(array,j,j+1);
                    flag = true;
                }
            }
            if(!flag){
                return;
            }
        }
    }
    //快速排序（挖坑法）
    public static void QuickSort(int[] array, int start, int end){

        if (start >= end){
            return;
        }
        
        int index = index(array,start,end);
        QuickSort(array,start,index-1);
        QuickSort(array,index+1,end);
    }
    public static int index(int[] array,int start,int end){
        int left = start;
        int right = end;
        int tmp = array[left];
        while (left < right){
            //从左向右找到比tmp小的下标
            while (left < right && array[right] >= tmp){
                right--;
            }
            //填坑
            array[left] = array[right];
            //从右向左找比tmp大的下标
            while (left < right && array[left] <= tmp){
                left++;
            }
            //填坑
            array[right] = array[left];
        }
        //最后将作为标准的值填入坑（形成tmp前都比tmp小，tmp后都比tmp大）
       array[right] = tmp;
        return right;
    }
    //交换方法
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
